//题目:
// 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
// 返回符合要求的 最少分割次数 。

// 示例 1：
// 输入：s = "aab"
// 输出：1
// 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

// 示例 2：
// 输入：s = "a"
// 输出：0

// 示例 3：
// 输入：s = "ab"
// 输出：1
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
    int arr[2001]={0};
public:
    // int dfs(const vector<vector<bool>>& dp,int y,int count)
    // {
    //     if(y==dp.size()) return count;

    //     if(arr[y]!=0) return arr[y];

    //     int min_count=INT_MAX;
    //     for(int i=dp.size()-1;i>=y;i--)
    //         if(dp[y][i]==true)
    //             min_count=min(min_count,dfs(dp,i+1,count+1));

    //     arr[y]=min_count;
    //     return min_count;
    // }
    int minCut(string s) 
    {
        int n=s.size();
        //一.找出s中所有的回文字符串
        //1.创建dp表————dp[i]表示：以s[i]为起点，s[j]为终点的字符串是否为回文字符串
        vector<vector<bool>> dp(n,vector<bool>(n));
        //2.初始化————无
        //3.填表
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
                if(s[i]==s[j] && (i==j || i+1==j || dp[i+1][j-1]!=0))
                    dp[i][j]=true;
        }
        //二.寻找最少分割次数 ———— 全排列 ———— 超时
        // int ret=INT_MAX;
        // for(int i=n-1;i>=0;i--)
        //     if(dp[0][i]==true)
        //         ret=min(ret,dfs(dp,i+1,0));

        //二.寻找最少分割次数 ———— 动态规划
        //1.创建dp表————arr[i]表示以s[i]为结尾的最少分割次数
        vector<int> arr(n);
        //2.初始化
        //3.填表
        for(int i=1;i<n;i++)
        {
            arr[i]=i;//最大分割次数
            if(dp[0][i]==true) arr[i]=0;
            else
            {
                for(int j=i-1;j>=0;j--)
                    if(dp[j+1][i]==true) 
                        arr[i]=min(arr[i],arr[j]+1);
            }
        }
        return arr[n-1];
    }
};